/*
   @Copyright:LintCode
   @Author:   tjyemail
   @Problem:  http://www.lintcode.com/problem/rotate-digits
   @Language: C++
   @Datetime: 19-05-13 11:25
   */

class Solution {
public:
	/**
	 * @param N: a positive number
	 * @return: how many numbers X from 1 to N are good
	 */
	int rotatedDigits(int N) {
		// write your code here
		int dict[]={0,1,5,-1,-4,2,9,-1,8,6};
		int count=0;
		char tmp[32];
		for(int i=0; i<=N; ++i){
			sprintf(tmp,"%d",i);
			bool found=true;
			for(char *p=tmp; *p!='\0'; ++p){
				if(dict[*p-'0']<0) {
					found=false;
					break;
				}
				*p=dict[*p-'0']+'0';
			}
			if(found && atoi(tmp)!=i) ++count;
		}
		return count;
	}
};
